package clsThree4;

public class LinearProbingHashST<Key, Value> {
    private int N;          // 符号表中键值对的总数
    private int M = 16;     // 线性探测表的大小
    private Key[] keys;     // 键
    private Value[] vals;   // 值

    // 构造函数
    public LinearProbingHashST() {
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }

    // 哈希函数
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    // 调整大小（具体实现请见 3.4.4 节）
    private void resize(int capacity) {
        // 实现逻辑请参考正文
    }

    // 插入键值对
    public void put(Key key, Value val) {
        if (N >= M / 2) resize(2 * M);  // 当元素数量达到容量的一半时，将 M 加倍
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                vals[i] = val;
                return;
            }
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }

    // 根据键获取值
    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return vals[i];
            }
        }
        return null;
    }
}